package 面试常见刷题;

import java.util.Arrays;

public class 堆排序 {

    public static void main(String[] args) {
        int[] ints = {1, 213, 12, 31, 41, 12};
        int[] ans = heapSort(ints);
        System.out.println(Arrays.toString(ans));
    }

    private static int[] heapSort(int[] data) {
        if(data.length<2) return data;
        int[] ans = new int[data.length];
        // 初始化的时候，从下往上的调整堆结构，首先找到最后一个非叶子节点。
        int leaveIndex = data.length/2-1;
        for (int i = leaveIndex; i >=0 ; i--) {
            adjustHeap(data,i,data.length);
        }
        // 交换根和最后一个位置，然后重新调整堆
        for (int i = 0; i < data.length; i++) {
            工具类.swap(data,0,data.length-1-i);
            ans[i] = data[data.length-1-i];
            adjustHeap(data,0,data.length-i-1);
        }
        return ans;
    }
    public static void adjustHeap(int[] data,int parentIndex,int length){
        // 如果父节点不是最大的那个，调整父节点为最大值并且调整与父节点交换的节点符合大根堆
        int maxIndex = parentIndex;
        int leftIndex = parentIndex*2+1,rightIndex = parentIndex*2+2;
        if(leftIndex<length&&data[leftIndex]>data[maxIndex]){
            maxIndex = leftIndex;
        }
        if(rightIndex<length&&data[rightIndex]>data[maxIndex]){
            maxIndex = rightIndex;
        }
        if(maxIndex!=parentIndex){
            工具类.swap(data,maxIndex,parentIndex);
            adjustHeap(data,maxIndex,length); // 调整左子树或者又子树为大根堆
        }

    }
}
